# 最大数： https://leetcode-cn.com/problems/largest-number/submissions/


class Solution:
    def largestNumber(self, nums: list) -> str:
        """
            就是将这些数字按照从大到小的顺序排列，然后转化为字符串输出
            注意： 这个比较的方法，需要重新实现。
            把两个数拼接到一起看谁大。 比如 4 ,23    423, 234  423大，则 4在23前面，4比23大
        """
        # 比较两数大小
        def Compare(x, y):
            a = int(str(x) + str(y))
            b = int(str(y) + str(x))

            if a > b:
                return True
            elif a < b:
                return False
            # return True if a > b else False
        
        # 使用快速排序
        def Pivotkey(nums, low, high):
            """ 使用三路分区 """
            pivotkey = nums[high]

            less = i = low
            great = high
            while i <= great:
                if Compare(nums[i], pivotkey):
                    nums[less], nums[i] = nums[i], nums[less]
                    less += 1
                    i += 1
                elif Compare(nums[i], pivotkey) == False:
                    nums[great], nums[i] = nums[i], nums[great]
                    great -= 1
                else:
                    i += 1

            return less, great    

        def QuickSort(nums, low, high):
            
            if low < high:
                lo, hi = Pivotkey(nums, low, high)
                QuickSort(nums, low, lo-1)
                QuickSort(nums, hi + 1, high)

        QuickSort(nums, 0, len(nums)-1)

        return ''.join(str(i) for i in nums) if nums[0] != 0 else  "0"


nums  = [8308,8308,830]       
s = Solution()
rst = s.largestNumber(nums)
print(rst)



